The traditional queue scheduling algorithm with weight is Weighted Round Robin (referred to as WRR), and the schematic diagram of WRR scheduling according to the related art is shown in FIG. 2. As shown in FIG. 2, when being sent to a queue, a message is first sent, according to its priority, to the queue of corresponding priority. When scheduling, queues with different priorities are selected according to a method of polling. The number of messages sent out is proportional to the weight of the queue in each cycle.
Each port is distributed into a plurality of output queues by way of WRR scheduling. These queues are scheduled in turn to ensure that each queue has a certain service time. At the same time, a weight is allocated to each queue, and the value thereof represents the ratio of resources acquired for that queue. Taking a 100 Mbps port as an example, the weight values of the WRR queue scheduling algorithms allocated to the port are 50, 30, 10, 10, so that the queue with the lowest priority is assured to obtain at least 10 Mbps bandwidth, thereby avoiding the disadvantage that messages in the queue with a low priority may not acquire any service for a long time when a Strict Priority scheduling is used.
Apparently, it is difficult for pure WRR algorithms to support length-varied flows, especially sudden flows. Therefore Deficit Weighted Round Robin (referred to as DWRR) algorithm emerges.
FIG. 3 is a schematic diagram of DWRR scheduling according to the related art, and as shown in FIG. 3, a weight value W and a weight middle value DC are set for each queue, so that the weight middle value DC is less than or equal to the weight value. A scheduler accesses each non-Empty queue, and if the packet length at the head of the queue is greater than DC, the scheduler moves to the next queue. If the packet at the head of the queue is less than or equal to DC, variable DC reduces the number of the bytes of the packet length, and transfers the packet to the output port. The scheduler continuously outputs packets and reduces the DC value, until the packet length at the head of the queue is greater than the value of the variable DC, and the residual DC value will be used as a credit value to be accumulated to the next polling. If the queue is Empty, DC is set to zero, and the scheduler will then service the next non-Empty queue.
DWRR can support scheduling for variable length messages and has a very good application perspective in engineering. But, how to achieve hardware implementation, especially a method that supports the easy expansion of the number of queues without changing the hardware implementation logic core, is always a hotspot for current research. It is very difficult for common binary tree implementation methods to support many queues, and the development difficulties are increased when the core logic has to be changed in order to expand the number of queues.
Currently, no effective solutions have been proposed for the problem that it is difficult to support the expansion of the number of queues and also difficult to implement the DWRR scheduling unit with less resource consumption in the precondition that the hardware implementation logic core is not changed.